class Solution {
    /*  
        贪心+二分查找(第一个大于a[i])的数
        
        新建一个 low 数组，low [ i ]表示长度为i的LIS结尾元素的最小值。
        对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。
        
        要点1：为什么要找第一个大于等于num的数?
            对于4,10,4  遍历到4的时候，ans=【4,10】，我们应该把4搞到index=0这个位置
    */
    public int lengthOfLIS(int[] nums) {
        int[] ans = new int[nums.length+1];
        int len = 1;
        ans[len] = nums[0];
        for(int i=1; i<nums.length; i++){
            int num = nums[i];
            if( num>ans[len] )
                ans[++len] = num;
            else{// 二分查找第一个大于等于（）num的数，然后覆盖它即可
                int l=1, r=len;
                int index = len;
                while( l<=r ){
                    int mid = (l+r)/2;
                    if( ans[mid]<nums[i]){
                        l = mid+1;
                    }else{
                        r = mid-1;
                        index = mid;
                    }
                }
                ans[index] = nums[i];
            }
        }
        return len;
    }
}
class Solution {
    /*
        时间复杂度：O（N*N）
    */
    public int lengthOfLIS(int[] nums) {
        int ans = 0;
        int[] count = new int[nums.length];
        for(int j=0; j<nums.length; j++){
            count[j] = 1;
            for(int i=0; i<j; i++){
                if( nums[j]>nums[i] ){
                    count[j] = Math.max(count[j],count[i]+1);
                }
            }
            ans = Math.max(ans,count[j]);
            // System.out.println(nums[j]+" "+ans);
        }
        return ans;
    }
}